package struts2demo.query.action;

import java.lang.Math;
import Jama.Matrix;
import java.io.*;
import java.util.ArrayList;

public class Clustering {
	static
	{
		System.loadLibrary("Clustering");
	}
	
	public native static void KMeans(int k);
	
	public Object[] kclustering(int k, ArrayList<Object> t) {
		//call clustering method in dll to do clustering
		KMeans(k);
		
		//read cdt file to matrix, is doc assign to cluster info
		try{
			BufferedReader reader = new BufferedReader(new FileReader("cluster_K_G3.kgg"));
			String line = reader.readLine();
			int group = -1;
			
			line = reader.readLine();
			String[] temp = line.split("	");
			while(line != null) {
				ArrayList<String> array = new ArrayList<String>();
				
				group = Integer.parseInt(temp[1]);
				array.add(temp[0]);

				while ( (line = reader.readLine()) != null ) {
					temp = line.split("	");
					int g = Integer.parseInt(temp[1]);
					
					if (g != group) break;
					else 
						array.add(temp[0]);
				}
				
				if (array.size() != 0)
					t.add(array);
			}
			reader.close();
		}
		catch (FileNotFoundException e) {
			System.out.println("kgg file can't be found!");
			System.exit(-1);
		}
		catch (IOException e) {
			System.out.println("IO Exception!");
			System.exit(-1);
		}
		
		int f = t.size();	//one matrix C for a cluster
		String[] terms = null;
		Matrix[] C = new Matrix[f];
		try{
			BufferedReader reader = new BufferedReader(new FileReader("cluster_K_G3.CDT"));
			String line = reader.readLine();
			String[] temp1 = line.split(" |	");
			terms = new String[temp1.length-3];
			for(int i = 0; i < temp1.length-3; i++)
				terms[i] = temp1[i+3];
				
			line = reader.readLine();
			line = reader.readLine();
			
			String[] temp = line.split("	");
			int column = temp.length-3;
			for(int i = 0; i < f; i++) {
				ArrayList<String> set = (ArrayList<String>)t.get(i);	
				int l = set.size();	//l rows
				
				C[i] = new Matrix(l, column);
				for(int j = 0; j < l; j++) {
					for(int m = 0; m < column; m++) 
						C[i].set(j, m, Double.parseDouble(temp[m+3]));
					
					if (j != l-1) {
						line = reader.readLine();
						temp = line.split("	");
					}
				}
				if (i != f-1) {
					line = reader.readLine();
					temp = line.split("	");
				}
			}
			reader.close();
		}
		catch (FileNotFoundException e) {
			System.out.println("CDT file can't be found!");
			System.exit(-1);
		}
		catch (IOException e) {
			System.out.println("IO Exception!");
			System.exit(-1);
		}
			
		Object[] r = new Object[2];
		r[0] = C;
		r[1] = terms;
		return r;
	}
	
	public void addEps(Matrix t, double e) {
		int m = t.getRowDimension(), n = t.getColumnDimension();
		for(int i = 0; i < m; i++)
			for(int j = 0; j < n; j++) {
				t.set(i, j, t.get(i, j)+e);
			}
	}
	
	public void NMF(Matrix A, Matrix W, Matrix H) {
		int m = A.getRowDimension(), n = A.getColumnDimension(), r = W.getColumnDimension();
		double threshold = Math.pow(0.1, 5.0);
		
		double sub = threshold+1, eps = Math.pow(0.1, 9);
		int repetition = 100, count = 0;
		while (sub > threshold && count < repetition) {
			Matrix W1 = W.transpose(), H1 = H.transpose();
			Matrix WA = W1.times(A), WH = W.times(H), WWH = W1.times(WH), AH = A.times(H1), WHH = WH.times(H1);
			
			//update W,H
			Matrix temp = AH.arrayRightDivide(WHH);
			W = W.arrayTimesEquals(temp);
			temp = WA.arrayRightDivide(WWH);
			H = H.arrayTimesEquals(temp);

			//update sub
			temp = A.minus(W.times(H));
			sub = 0.;
			for(int i = 0; i < m; i++)
				for(int j = 0; j < n; j++) {
					sub += temp.get(i,j)*temp.get(i,j);
				}
			count++;
		}
	}
	
	public double sim(double[] w, double[] T) {
		int n = w.length;
		double r = 0., t1 = 0., t2 = 0.;
		for(int i = 0; i < n; i++) {
			r += w[i]*T[i];
			t1 += w[i]*w[i];
			t2 += T[i]*T[i];
		}
		
		if (t1 != 0. && t2 != 0.)
			r = r/(Math.sqrt(t1)*Math.sqrt(t2));
		return r;
	}
	
	//return the indexes of top k items in the set, assume set is longer than k
	public int[] topk(int k, double[] set) {
		int[] result = new int[k];
		
		double max = Double.MAX_VALUE;
		
		for(int i = 0; i < k; i++) {
			double store = -1.;
			int temp = -1;
			for(int j = 0; j < set.length; j++) {
				if (set[j] <= max && set[j] > store) {
					boolean in = false;
					int e = i-1;
					while(e != -1 && set[j] == set[result[e]]) {
						if (j == result[e]){
							in = true;	break;
						}
						e--;
					}
					
					if (!in) {
						temp = j;
						store = set[j];
					}
				}
			}
			result[i] = temp;
			max = store;
		}
		
		return result;
	}
	
	public int[][][] getWinners(Matrix[] m) {
		int f = m.length, N = 0;	
		
		for(int i = 0; i < f; i++)
			N += m[i].getColumnDimension();
		int k = (int)(N*0.9);
		int[] s = new int[f];
		for(int i = 0; i < f; i++)
			s[i] = (int)Math.floor((m[i].getColumnDimension())*k/N);
			
		//get topics from cluster
		int[][] topics = new int[f][];	//f topic vectors
		double[][] T = new double[f][];
		for(int i = 0; i < f; i++) {
			int l = m[i].getRowDimension();
			double[] d = new double[l];
			for(int t = 0; t < l; t++)
				for(int j = 0; j < m[i].getColumnDimension(); j++) 
					d[t] += m[i].get(t, j);
				
			topics[i] = topk(3, d);
			T[i] = new double[m[i].getRowDimension()];	//set T
			T[i][topics[i][0]] = d[topics[i][0]];
			T[i][topics[i][1]] = d[topics[i][1]];
			T[i][topics[i][2]] = d[topics[i][2]];
		}
		
		Matrix[] W = new Matrix[f];
		Matrix[] H = new Matrix[f];
		for(int i = 0; i < f; i++) {
			int r = T[i].length;
			double[] kt= new double[m[i].getRowDimension()*r];
			for(int j = 0; j < m[i].getRowDimension()*r; j++)
				kt[j] = Math.random();
			W[i] = new Matrix(kt, m[i].getRowDimension());
			kt = new double[r*m[i].getColumnDimension()];
			for(int j = 0; j < r*m[i].getColumnDimension(); j++)
				kt[j] = Math.random();
			H[i] = new Matrix(kt, r);
			
			NMF(m[i], W[i], H[i]);
		}
			
		//pick top s[i] pages from cluster
		int[][] result = new int[f][];	//f list, every contain the index of document in descending order
		for(int i = 0; i < f; i++) {
			int r = W[i].getColumnDimension();
			double[] similar = new double[r];
			for(int j = 0; j < r; j++) {
				Matrix B = new Matrix(r, 1);
				B.set(j, 0, 1);
				B = W[i].times(B);
				double[] wj = B.getRowPackedCopy();
				similar[j] = sim(wj, T[i]);
			}
			
			int[] p = topk(s[i], similar);
			result[i] = new int[s[i]];
			for(int j = 0; j < s[i]; j++) {
				int temp = 0;
				double store = H[i].get(p[j], 0);
				for(int t = 1; t < H[i].getColumnDimension(); t++) {
					double temp1 = H[i].get(p[j], t);
					if (temp1 > store) {
						temp = t;
						store = temp1;
					}
				}
				result[i][j] = temp;
			}
		}
		
		int[][][] r = new int[2][][];
		r[0] = result;
		r[1] = topics;
		return r;
	}
	
	public Matrix getOriginMatrix() {
		ArrayList<double[]> sets = new ArrayList<double[]>();
		int column = -1;
		try{
			BufferedReader reader = new BufferedReader(new FileReader("frequency.txt"));
			String line = reader.readLine();
			String[] temp = line.split("	");
			column = temp.length;
			
			while(line != null && !line.equals("")) {
				temp = line.split("	");
				double[] d = new double[column];
				for(int i = 0; i < column; i++) 
					d[i] = Double.parseDouble(temp[i]);
				sets.add(d);
				line = reader.readLine();
			}
			reader.close();
		}
		catch (FileNotFoundException e) {
			System.out.println("Frequency file can't be found!");
			System.exit(-1);
		}
		catch (IOException e) {
			System.out.println("IO Exception!");
			System.exit(-1);
		}
		
		int row = sets.size();
		double[][] values = new double[row][];
		for(int i = 0; i < row; i++) 
			values[i] = sets.get(i);
		Matrix A = new Matrix(values, row, column);
		return A.transpose();
	}
	
	public Matrix getTransform(Matrix A, Matrix[] m) {
		int row = A.getRowDimension();
		double[] t1 = new double[row];
		Matrix A1 = new Matrix(t1, row);
		int N = 0;
		for(int i = 0; i < m.length; i++)
			N += m[i].getColumnDimension();
		for(int i = 0; i < m.length; i++) {
			for(int k = 0; k < row; k++) {
				for(int j = 0; j < m[i].getColumnDimension(); j++) {
					t1[k] += m[i].get(k, j);
				}
				t1[k] = t1[k]*N/(N-1);
			}
		}
		Matrix A2 = new Matrix(t1, row);
		A2.print(A2.getRowDimension(), A2.getColumnDimension());
		
		Matrix temp = new Matrix(A.getColumnDimension(), 1);
		for(int j = 0; j < A.getColumnDimension(); j++)
			temp.set(j, 0, 1);
		A1 = A.times(temp);
		A1.print(A1.getRowDimension(), A1.getColumnDimension());
		
		return A2.solveTranspose(A1);
	}
	
	public String[][][] extract() {
		int k = 3;
		ArrayList<Object> docID = new ArrayList<Object>();
		Object[] o = kclustering(k, docID);
		Matrix[] m = (Matrix[])o[0];
		String[] terms = (String[])o[1];
		
		int f = m.length;
		for(int i = 0; i < f; i++)
			m[i] = m[i].transpose();	//row: term, column: doc
		int[][][] result = getWinners(m);	//the index is relative to each m[i](cluster)
		String[][] docCluster = new String[f][];
		int[][] docs = result[0];
		for(int i = 0; i < f; i++) {
			int l = docs[i].length;
			docCluster[i] = new String[l];
			ArrayList<String> di = (ArrayList<String>)docID.get(i);
			for (int j = 0; j < l; j++) {
				docCluster[i][j] = di.get(docs[i][j]);
			}
		}
		docs = result[1];	//analyze topics
		String[][] topics = new String[f][];
		for(int i = 0; i < f; i++) {
			topics[i] = new String[docs[i].length];
			for(int j = 0; j < docs[i].length; j++) 
				topics[i][j] = terms[docs[i][j]];
		}
		
		
		//Matrix A = getOriginMatrix();	//row: term, column: doc
		
		/*
		A.print(A.getRowDimension(), A.getColumnDimension());
		for(int i = 0; i < f; i++)
			m[i].print(m[i].getRowDimension(), m[i].getColumnDimension());
			*/
		/*
		Matrix t = getTransform(A, m);	//for exchange row
		t.print(t.getRowDimension(), t.getColumnDimension());
		Matrix[] V = new Matrix[f];
		for(int i = 0; i < f; i++) {
			Matrix temp = m[i].times(t);
			V[i] = temp.solveTranspose(A);
		}
		
		int[][] pages = result[0];
		Matrix[] U = new Matrix[f];	//the page id in A, order is represented by weight from l to 1
		double[][] pagecluster = new double[f][A.getColumnDimension()];
		for(int i = 0; i < f; i++) {
			int l = pages[i].length, n = m[0].getColumnDimension();
			double[][] d = new double[1][n];//Vector : U
			for(int j = 0; j < l; j++) 
				d[0][pages[i][j]] = l-j;
			U[i] = new Matrix(d, 1, n);
			U[i].times(V[i]);
			pagecluster[i] = U[i].getRowPackedCopy();
		}
		*/
		
		String[][][] r = new String[2][][];
		r[0] = docCluster;
		r[1] = topics;
		return r;
	}
		
	public static void main(String[] args) {
		Clustering c = new Clustering();
		String[][][] result = c.extract();
		String[][] docs = result[0];
		for(int i = 0; i < docs.length; i++) {
			for(int j = 0; j < docs[i].length; j++) 
				System.out.print(docs[i][j]+"	");
			System.out.println("");
		}
		docs = result[1];
		for(int i = 0; i < docs.length; i++) {
			for(int j = 0; j < docs[i].length; j++) 
				System.out.print(docs[i][j]+"	");
			System.out.println("");
		}
	}

}